﻿// See https://aka.ms/new-console-template for more information
//List<T> 动态数组
//核心特性：
//1.底层结构：基于数组实现，内存连续分配
//2.动态扩容：当元素数量达到内容上限时，新建一个容量翻倍的数组
//将旧数据拷贝到新数组
//3.通过索引访问
//时间复杂度：
//从尾部插入/删除：O（1）
//从中间插入/删除：O（n）
//查找元素：O（n）
//性能注意：
//1.预分配容量，可避免频繁扩容
//2.尾部操作效率最高，中间操作尽量避免

// class Program
// {
//     static void Main()
//     {
//List创建并初始化
// List<string> cities = new List<string> { "北京", "上海" };
// //添加元素
// cities.Add("广州");
// //插入元素
// cities.Insert(1, "深圳");
// //删除指定元素
// cities.Remove("上海");
// //删除指定索引元素
// cities.RemoveAt(0);
// //遍历
// Console.WriteLine("当前城市列表：");
// foreach (string city in cities)
// {
//     Console.WriteLine(city);
// }

// //其他操作
// Console.WriteLine($"是否包含广州：{cities.Contains("广州")}");
// Console.WriteLine($"第二个元素：{cities[1]}");

//双线链表：LinkedList<T>
//核心特性：
//基于节点链接实现
//每个节点都包含 Previous、 Next指针和Value
//插入删除效率高
//不支持索引访问

//时间复杂度
//插入删除：O（1）
//查找：O（n）
//使用场景：
//需要频繁在集合中进行插入删除操作

//创建初始化
// LinkedList<int> scores = new LinkedList<int>();

// //尾部添加
// scores.AddLast(90);
// //头部添加
// scores.AddFirst(80);
// //在指定元素前插入
// LinkedListNode<int> node = scores.Find(90);
// scores.AddBefore(node, 85);
// //删除
// scores.Remove(80);

// //遍历
// Console.WriteLine("当前分数链表:");
// foreach (int score in scores) {
//     Console.WriteLine(score);
// }

//队列 Queue<T>
//核心特性
//1.先进先出规则
//2.底层结构：基于数组实现，使用两个指针head和tail
//使用场景：需要顺序处理的场景，如任务队列

//创建并初始化
// Queue<string> tasks = new Queue<string>();
// //入队
// tasks.Enqueue("处理订单");
// tasks.Enqueue("发送邮件");
// tasks.Enqueue("生成报表");
// //出队
// Console.WriteLine("当前任务队列：");
// while (tasks.Count > 0)
// {
//     string currentTask = tasks.Dequeue();
//     Console.WriteLine($"正在处理：{currentTask}");
// }

//栈 Stack<T>
//核心特性：
//1.严格遵循后进先出规则
//2.基于数组实现，使用栈顶指针
//时间复杂度
//压栈、弹栈：O（1）
//压栈操作：向数组尾部追加元素
//弹栈操作：从数组尾部移除元素
//适用场景：需要反向处理的场景

// Stack<char> chars = new Stack<char>();
// //压栈
// chars.Push('A');
// chars.Push('B');
// chars.Push('C');
// //弹栈
// Console.WriteLine("弹栈顺序：");
// while (chars.Count>0) {
//     Console.WriteLine(chars.Pop());
// }





//Dictionary<Key,Value>
//核心特性：
//1.键值对存储，键唯一
//2.基于哈希表实现，快速查找
//时间复杂度：平均：O（1），最坏：O（n）
//创建并初始化
// Dictionary<int, string> employees = new Dictionary<int, string>();
// //添加数据
// employees.Add(1001, "张三");
// employees[1002] = "李四";//索引器方式
// //安全访问
// if (employees.TryGetValue(1001, out string name))
// {
//     Console.WriteLine($"员工1001：{name}");
// }
// //遍历
// Console.WriteLine("---------------");
// foreach (KeyValuePair<int, string> kvp in employees)
// {
//     Console.WriteLine($"{kvp.Key}:{kvp.Value}");
// }
// //删除
// employees.Remove(1002);


//HashSet<T>
//核心特性
//1.与字典类似，但是只存储键（T作为键，值占位）
//2.元素唯一，自动去重
//3.基于哈希表实现
//4.支持集合运算

//创建并初始化
// HashSet<int> setA = new HashSet<int> { 1, 2, 3 };
// HashSet<int> setB = new HashSet<int> { 3, 4, 5 };

// //集合运算
// setA.UnionWith(setB);//并集
// setA.IntersectWith(setB);//交集
// //遍历
// foreach (int num in setA)
// {
//     //TODO
// }

// //判断是否包含
// Console.WriteLine($"是否包含3：{setA.Contains(3)}");

//PriorityQueue<Element,Priority>
//核心特性：
//1.元素优先级分离：每个元素Element关联一个优先级Priority
//2.出队顺序：总是返回当前队列中优先级最高的元素
//3.动态排序：插入新元素时会自动调整堆结构
//4.非线程安全：需要自行处理多线程同步

//默认构造，使用优先级类型的默认比较器
//         PriorityQueue<string, int> pq1 = new PriorityQueue<string, int>();
//         //自定义优先级比较器
//         var pq2 = new PriorityQueue<string, int>(
//             Comparer<int>.Create((x, y) => y.CompareTo(x))//降序
//         );

//         var pqs = new PriorityQueue<string, int>();
//         pqs.Enqueue("pqA", 3);//数字越小，优先级越高
//         pqs.Enqueue("pqB", 1);
//         pqs.Enqueue("pqc", 2);

//         Console.WriteLine($"队列元素数量：{pqs.Count}");
//         //查看但不移除
//         Console.WriteLine($"下一个处理：{pqs.Peek()}");
//         //移除并返回最高优先级元素
//         while (pqs.TryDequeue(out var patient, out var priority))
//         {
//             Console.WriteLine($"处理：{patient}(优先级：{priority})");
//         }

//         //批量操作
//         PriorityQueue<string, DateTime> task = new PriorityQueue<string, DateTime>();
//         task.EnqueueRange(
//             new[]{
//                 ("写报告",DateTime.Now.AddDays(3)),
//                 ("写代码",DateTime.Now.AddHours(1)),
//                 ("开会",DateTime.Now.AddMinutes(30))
//             }
//         );
//         Console.WriteLine(task.Count);
//         task.Dequeue();
//         Console.WriteLine(task.Count);
//         //清空
//         task.Clear();
//         Console.WriteLine(task.Count);
//     }
// }

MyLinkedList<string> list = new MyLinkedList<string>();
list.AddLast("A");
list.AddLast("B");
foreach (string score in list)
{
    Console.WriteLine(score);
}
list.Remove("A");
foreach (string score in list) {
    Console.WriteLine(score);
}

//手动实现双向链表
public class MyLinkedList<T>
{
    private class Node
    {
        public T Value;
        public Node Next;
        public Node Prev;
    }

    private Node _head;
    private Node _tail;

    //时间复杂度：O（1）
    public void AddLast(T value)
    {
        var newNode = new Node { Value = value };
        if (_tail == null)
        {
            _head = _tail = newNode;
        }
        else
        {
            newNode.Prev = _tail;
            _tail.Next = newNode;
            _tail = newNode;
        }
    }

    public bool Remove(T value)
    {
        Node current = _head;
        while (current != null)
        {
            if (EqualityComparer<T>.Default.Equals(current.Value, value))
            {
                if (current.Prev != null) current.Prev.Next = current.Next;
                if (current.Next != null) current.Next.Prev = current.Prev;
                if (current == _head) _head = current.Next;
                if (current == _tail) _tail = current.Prev;
                return true;
            }
            current = current.Next;
        }
        return false;
    }

    //实现迭代器
    public IEnumerator<T> GetEnumerator()
    {
        Node current = _head;
        while (current != null)
        {
            yield return current.Value;
            current = current.Next;
        }
    }
}

